/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param root: A Tree
     * @return: Preorder in ArrayList which contains node values.
     */
    
    //法一：递归 142 ms
    // vector<int> preorderTraversal(TreeNode * root) {
    //     vector<int> result;
    //     traverse(root, result);
    //     return result;
    // }
    // void traverse(TreeNode *node, vector<int>& result) 
    // {
    //     if (!node)
    //     {
    //         return;
    //     }
    //     result.push_back(node->val);
    //     traverse(node->left, result);
    //     traverse(node->right, result);
    // }
    
    // 法二：非递归 栈1
    // vector<int> preorderTraversal(TreeNode *root) 
    // {
    //     vector<int> result;
    //     if (!root)
    //     {
    //         return result;
    //     }
    //     stack<TreeNode*> s;
    //     TreeNode* tmp = root;
    //     while (tmp || !s.empty())
    //     {
    //         while (tmp)
    //         {
    //             s.push(tmp);
    //             result.push_back(tmp->val); //和中序遍历唯一区别
    //             tmp = tmp->left;
    //         }
    //         tmp = s.top();
    //         s.pop();
    //         tmp = tmp->right;
    //     }
    // }
    
    // 法三：（推荐）非递归 栈2 98 ms
    // vector<int> preorderTraversal(TreeNode *root) 
    // {
    //     vector<int> result;
    //     if (!root)
    //     {
    //         return result;
    //     }
    //     stack<TreeNode*> s;
    //     TreeNode *tmp = root;
    //     s.push(root);
    //     while (!s.empty())
    //     {
    //         tmp = s.top();
    //         s.pop();
    //         result.push_back(tmp->val);
    //         if (tmp->right)
    //         {
    //             s.push(tmp->right);
    //         }
    //         if (tmp->left)
    //         {
    //             s.push(tmp->left);
    //         }
    //     }
    //     return result;
    // }

    //非递归（推荐）。 按规律：左子树最右结点后面是右子树第一个节点。时间复杂度？ 
    vector<int> preorderTraversal(TreeNode * root) {
        vector<int> result;
        while (root)
        {
            result.push_back(root->val);
            if (root->left)
            {
                TreeNode *pre = root->left;
                while (pre->right)
                {
                    pre=pre->right;
                }
                pre->right=root->right;
                root->right=root->left;
                root->left=NULL;
            }
            root=root->right;
        }  
        return result;
    }
};